//给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 20
//输出：1
//解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
// 
//
// 示例 2： 
//
// 
//输入：n = 100
//输出：10
//解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
// 
//
// 示例 3： 
//
// 
//输入：n = 1000
//输出：262
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10⁹ 
// 
// Related Topics数学 | 动态规划 
//
// 👍 124, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class NumbersWithRepeatedDigits {
    public static void main(String[] args) {
        Solution solution = new NumbersWithRepeatedDigits().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        char[] s;
        int[][] memo;

        // 数位DP
        // https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/solution/by-lfool-epqy/
        public int numDupDigitsAtMostN(int n) {
            s = String.valueOf(n).toCharArray();
            int m = s.length;
            memo = new int[m][1024];
            for (int i = 0; i < m; i++) {
                Arrays.fill(memo[i], -1);
            }

            // 结果取反
            return n - f(0, 0, true, false);
        }

        // 表示没有重复的字数的个数，最后 n - f() 即可
        // mask 大小为 1024，长度为 10 位，记录 0 - 9 选择的情况，若 i 已选择，则 mask 中第 i 位为 1
        // isNum:这里引入一个新的参数 isNum，表示 i 前面是否已经选了数字。isNum 主要的作用是过滤掉「前导零」，如果对「前导零」没有要求，则可以不使用该参数。例如:0001 和 1 是同一个数字
        public int f(int i, int mask, boolean isLimit, boolean isNum) {
            if (i == s.length) return isNum ? 1 : 0;

            if (!isLimit && isNum && memo[i][mask] != -1) return memo[i][mask];

            // 下界，如果前面有数字，例如:1 0~9，如果没有数字 000 1~9
            int down = isNum ? 0 : 1;
            int up = isLimit ? s[i] - '0' : 9;

            // f(i + 1, mask, false, false) 表示仍然不选择，可以跳过当前数字，如果要选择，那么从1开始
            int res = isNum ? 0 : f(i + 1, mask, false, false);

            // 如果选择
            for (int j = down; j <= up; j++) {
                // 如果j没有被选择过
                if (((mask >> j) & 1) == 0) {
                    res += f(i + 1, mask | (1 << j), isLimit && j == up, true);
                }
            }

            if (!isLimit && isNum) memo[i][mask] = res;
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
